正则表达式匹配

Posted on | | reads times

正则表达式匹配

题目描述

请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

  • 第二个字符为”*”
    • 第一个字符为”.”或为等于s此时的字符
    • 第一个字符不为”.”且第一个字符也不匹配s此时的字符
  • 第二个字符不为”*”
    • 第一个字符为”.”或第一个字符匹配s此时的字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function match(s, pattern)
{
    // write code here
    if(s==null||pattern==null)return false;
    return matchrecursive(s,0,pattern,0);
}
function matchrecursive(str,istr,pattern,ipattern){
    if(str.length==istr&&pattern.length==ipattern)
        return true;
    if(str.length!=istr&&pattern.length==ipattern){
        return false;
    }
    if(pattern[ipattern+1]=='*'){
        if(pattern[ipattern]=='.'&&istr!=str.length||pattern[ipattern]==str[istr]){
            return (
                matchrecursive(str,istr+1,pattern,ipattern+2)||
                matchrecursive(str,istr+1,pattern,ipattern)||
                matchrecursive(str,istr,pattern,ipattern+2)
            )
            
        }
        return matchrecursive(str,istr,pattern,ipattern+2)
    }
    if(pattern[ipattern]=='.'&&istr!=str.length||pattern[ipattern]==str[istr]){
        return matchrecursive(str,istr+1,pattern,ipattern+1)
    }
    return false;
}